package com.myc.subjects.hashmap;

import com.sun.org.apache.xpath.internal.operations.Bool;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * LeetCode题号：128
 *
 * 最长连续序列
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
 *
 * 示例 1：
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 *
 * 示例 2：
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 *
 * 提示：
 * 0 <= nums.length <= 104
 * -109 <= nums[i] <= 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Zuichanglianxuxulie {

    public static void main(String[] args) {
        int[] nums = new int[]{100,4,200,1,3,2};
        Zuichanglianxuxulie zuichanglianxuxulie = new Zuichanglianxuxulie();
        System.out.println(zuichanglianxuxulie.longestConsecutive1(nums));
    }

    /**
     * 方法一：暴力法
     * 时间复杂度：O(n^3)
     * 遍历数组，对于每一个元素 n 找到数组是否包含下一个元素 n+1，存在则统计长度 + 1,循环调用，直到找不到为止
     */
    public int longestConsecutive1(int[] nums) {
        int result = 0;//定义结果
        for(int i = 0; i < nums.length; i++){
            int count = 1;//定义长度统计值，起始为1，因为第i个元素已经是占了一个位置
            int num = nums[i];
            while(contains(nums, ++num)){//循环判断是否包含 num + 1
                count++;
            }
            if(result < count) result = count;//使用count最大的那个值作为结果返回
        }
        return result;
    }

    public boolean contains(int[] nums, int num){
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == num) return true;
        }
        return false;
    }

    /**
     * 方法二：使用HashSet
     * 时间复杂度：O(n)
     * 利用经典时间降维策略，使时间复杂度将一个维度。
     * 在遍历每一个元素时，判断这个元素是不是一个序列的起始元素，是，则开始统计序列长度，不是则跳过,这样又可使时间复杂度降一个维度
     */
    public int longestConsecutive2(int[] nums) {
        //定义一个HashSet，将nums中的元素放入set中
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }

        int result = 0;
        for(int i = 0; i < nums.length; i++){
            if(!set.contains(nums[i] - 1)){//判断元素是否是序列的起始元素，就是看nums[i] - 1在set中是否存在
                int num = nums[i];
                int count = 1;
                while(set.contains(++num)){//经典时间降维策略
                    count++;
                }
                if(result < count) result = count;
            }
        }
        return result;

    }

    /**
     * 方法三：使用HashMap
     * 时间复杂度：O(n)
     * 定义一个HashMap，将nums中值作为键，nums中的值是否使用过的布尔值作为值存入该HashMap
     * 在遍历数组每个元素的时候，发现这个元素已经使用过了，则不再考虑，直接跳过。
     * 在统计序列长度的时候，先循环统计是否存在num[i] - 1，如果存在，统计长度 + 1，同时将元素标记为已使用，再循环统计num[i] + 1
     */
    public int longestConsecutive3(int[] nums) {
        //定义HashMap，键为nums中的每个元素，值为是否使用过
        Map<Integer, Boolean> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], false);//值初始值为false
        }
        int result = 0;
        for(Integer num : map.keySet()){
            if(!map.get(num) == true) {
                map.put(num, true);
                int sum = 1;
                int curr = num;
                while(map.containsKey(--curr)){//先循环判断是否存在curr-1
                    sum++;
                    map.put(curr, true);//标记为已使用
                }
                while(map.containsKey(++num)){//再循环判断是否存在num-1
                    sum++;
                    map.put(num, true);//标记为已使用
                }
                if(result < sum) result = sum;
            }
        }
        return result;
    }

    //官方题解
    public int longestConsecutiveOfficial(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

}

/**
 * 总结：
 * 1.利用经典时间降维策略，减低时间复杂度
 * 2.仔细研究每一次遍历，找出是否出现重复遍历的部分，用其他方法避免重复遍历
 */
